1. Field of the Invention
The invention relates to the technical field of cryptography, and more precisely to what is called public key cryptography. In this type of cryptography, a user owns a pair of keys for a given use. Said pair of keys consists of a private key that this user keeps secret and an associated public key that this user may communicate to other users. For example, in the case of a pair of keys dedicated to confidentiality, the public key is then used to encipher the data, whereas the secret key is used to decipher it, that is to say to re-establish this data in clear.
2. Related Art
Public key cryptography is very widely used insofar as, unlike secret key cryptography, it does not require the interlocutors to share the same secret in order to establish a security-protected communication. However, this advantage in terms of security is accompanied by a disadvantage in terms of performance, since public key cryptography methods, also called “public key schemes”, are often one hundred or one thousand times slower than secret key cryptography methods, also called “secret key schemes”. A very great challenge is therefore to find public key cryptography methods that can be rapidly executed so as to be able to use them in resource-limited environments, such as standard microprocessor cards, with or without contacts.
Most public key schemes existing at the present time rely on the difficulty of mathematical problems in the field of arithmetic (or “number theory”). Thus, the security of the RSA (Rivest, Shamir, Adleman) numerical signature and encryption scheme is based on the difficulty of the problem of factorizing integers: given a very large integer (having more than 500 bits) obtained privately by multiplying together two or more prime numbers of comparable size, no effective method exists at the present time for recovering these prime numbers.
Other public key schemes, such as the ElGamal digital signature or encryption scheme, rely for their security on the difficulty of what is called the “discrete logarithm problem”. This problem may be expressed in its most general case as follows: let E be a set provided with an operation (i.e. with a function which, having two elements a and b, associates an element denoted “a.b” or “ab”, and called the “product of a and b”), let g be an element of E, let r be a large integer and let y be the integer defined by: y=gr (that is to say the product g·g· . . . ·g, with g occurring r times); it is then unfeasible to recover r from g and y.
The invention relates more particularly to the technical field of entity authentication, also called “identification”, and also that of the authentication of a message and of its digital signature by means of public key cryptographic techniques. In such methods, the authenticated entity, called the “prover” possesses a secret or private key and an associated public key. The prover uses the secret key to produce an authentication value. The authenticating entity, called the “verifier”, needs only the public key of the prover to verify the authentication value.
The invention relates more particularly still to authentication methods called “zero-knowledge disclosure”. This means that the authentication takes place using a protocol which, in a proven manner, reveals nothing about the secret key of the authenticated entity, this being so however many times it is used. From this type of scheme it is known how to deduce, using standard techniques, schemes for authenticating a message and a digital signature of this message.
The invention relates even more particularly to methods whose security relies both on the difficulty of the problem of factorizing integers and that of the discrete logarithm problem.
The invention is applicable in any system using public key cryptography to protect the security of their elements and/or their transactions, and more particularly in systems in which the number of calculations performed by the various parties constitutes, at least for one of them, a critical parameter, either because it does not have available a coprocessor specialized in cryptographic calculations, often called a “cryptoprocessor”, so as to speed up the calculations, or because it is capable of carrying out a large number of calculations simultaneously, for example in the case of central server, or for any other reason.
A typical application is electronic payment, by bank card or by electronic purse. In the case of proximity payment, the payment terminal is in a public place, prompting the use of public key cryptography methods, so as not to store a master key. To reduce the overall costs of such a system, it may be desirable either for the card to be a standard microprocessor card, that is to say a card not provided with a cryptoprocessor, or for the security-protected microprocessor contained in the terminal itself to be of standard type, or for both of these. Depending on the case and on the cryptographic method adopted, the prior art known at the present time does achieve one or other of these objectives, but does not allow both to be easily achieved simultaneously, while complying with the constraints of the system. An example of such a constraint is that the payment shall be effected in less than one second, or even in less than 150 milliseconds in the case of a contactless transaction, or even in a few milliseconds in the case of a motorway tollgate.
One limitation of all the cryptographic methods known hitherto is that the number of calculations that each of the parties has to perform is fixed by the method itself and cannot be modified. In particular, it is not possible to vary the distribution of the calculations between the prover and a third party not necessarily in confidence, so as to adapt to such or such an environment. This prevents the same method from being able to be used in a variety of environments in which the constraints are different.